
import struct
import thread
import warnings

SURPRESS_WARNINGS = False

# Lump indices

lumps = ['Entities',
 'Planes',
 'Texdata',
 'Vertexes',
 'Visibility',
 'Nodes',
 'Texinfo',
 'Faces',
 'Lighting',
 'Occlusion',
 'Leafs',
 'Unused',
 'Edges',
 'Surfedges',
 'Models',
 'Worldlights',
 'LeafFaces',
 'LeafBrushes',
 'Brushes',
 'Brushsides',
 'Areas',
 'AreaPortals',
 'Portals',
 'Clusters',
 'PortalVerts',
 'Clusterportals',
 'Dispinfo',
 'OriginalFaces',
 'Unused',
 'PhysCollide',
 'VertNormals',
 'VertNormalIndices',
 'DispLightmapAlphas',
 'DispVerts',
 'DispLightmapSamplePos',
 'GameLump',
 'LeafWaterData',
 'Primitives',
 'PrimVerts',
 'PrimIndices',
 'Pakfile',
 'ClipPortalVerts',
 'Cubemaps',
 'TexdataStringData',
 'TexdataStringTable',
 'Overlays',
 'LeafMinDistToWater',
 'FaceMacroTextureInfo',
 'DispTris',
 'PhysCollideSurface',
 'Unused',
 'Unused',
 'Unused',
 'LightingHDR',
 'WorldlightsHDR',
 'LeaflightHDR1',
 'LeaflightHDR2',
 'Unused',
 'Unused',
 'Unused',
 'Unused',
 'Unused',
 'Unused',
 'Unused']

class BSPReadOnlyError(Exception): pass

class BSPNoSuchLumpError(Exception): pass

class BSPWrongMagicNumberError(Exception): pass

class BSPWarning(Warning): pass

def warn(info):
    if not SURPRESS_WARNINGS:
        warnings.warn(str(info), BSPWarning)

# Shift binary numbers into ascii text 
def shift_to_ascii(i):
    ascii = ''
    for x in (24, 16, 8):
        num = i >> x
        ascii = chr(num) + ascii
        i -= num << x
    return chr(i) + ascii
    
    
class Reader:
    def __init__(self, fileobj):
        self.__format_cache = {}
        self.f = fileobj

    def read(self, format='', offset=None):
        if offset:
            self.f.seek(offset)
        if format:
            result = struct.unpack(format, self.f.read(self.getsize(format)))
            if len(result) == 1:
                return result[0]
            return result
    
    def getsize(self, format):
        if format in self.__format_cache:
            return self.__format_cache[format]
        size = struct.Struct(format).size
        self.__format_cache[format] = size
        return size
    

class BSP:
    """
    Main class holding all the information gathered from the BSP file
    """
    def __init__(self, filename, threaded_parsing=False):
        self.filename = filename
        self.f = open(self.filename, 'rb')
        self.reader = Reader(self.f)
        self.read = self.reader.read
        if '/' in filename:
            name = filename.rsplit('/',1)[1]
        elif '\\' in filename:
            name = filename.rsplit('\\',1)[1]
        else:
            name = filename
        self.name = name
        self.readHeaders()
        if not self.d_headers['ident'] == 'VBSP': # Only support Valve BSPs!
            raise BSPWrongMagicNumberError, self.d_headers['ident']
        self.headers = BSPHeaders(self.d_headers, name)
        self.body = BSPBody(self.reader, self.headers, name)
        if threaded_parsing: # Experimental!
            warn('FIXME: Threading support is experimental')
            thread.start_new_thread(self.parseall, tuple())
            
    def readHeaders(self):
        """
        converts the headers into a dictionary and returns them as well as the full
        body.
        """
        # Our struct string of the headers
        """
        i       ident
        i       version
        iii4s   (64 times) lumps headers:
            i       fileofs
            i       filelen
            i       version
            4s      fourCC
        i       map revision
        """
        self.d_headers = {}
        self.d_headers['ident'] = shift_to_ascii(self.read('i'))
        self.d_headers['version'] = self.read('i')
        self.d_headers['lumps'] = {}
        for x in range(64):
            self.d_headers['lumps'][lumps[x]] = {}
            self.d_headers['lumps'][lumps[x]]['fileofs'] = self.read('i')
            self.d_headers['lumps'][lumps[x]]['filelen'] = self.read('i')
            self.d_headers['lumps'][lumps[x]]['version'] = self.read('i')
            self.d_headers['lumps'][lumps[x]]['fourCC'] = self.read('4s')
        self.d_headers['mapRevision'] = self.read('i')
    
    def __getitem__(self, item):
        if item == 'body':
            return self.body
        if item == 'headers':
            return self.headers
        if item in lumps:
            return self.body[item]
        if item in self.d_headers:
            return self.d_headers[item]
        if item in self.d_headers['lumps']:
            return self.d_headers['lumps'][item]
        
    def __getattr__(self, attr):
        return self.__getitem__(attr)
    
    @staticmethod
    def __len__():
        return 2
    
    @staticmethod
    def keys():
        return ['headers','body']
        
    def parse(self, lumpname):
        self.body.parse(lumpname)
        
    def parseall(self):
        self.body.parseall()
        
    def __repr__(self):
        return 'bsplib.BSP of %s' % self.name
    
    def getDict(self):
        self.parseall()
        return {'headers': self.d_headers, 'body': self.body.getDict()}
    
    def __str__(self):
        return str(self.getDict())
        

class ReadOnly(object):
    @staticmethod
    def __setattr__(item):
        raise BSPReadOnlyError
    __setitem__ = __setattr__
    
    
class BSPHeaders(ReadOnly):
    def __init__(self, dictionary, name):
        self.__dict__['name'] = name
        self.__dict__['dictionary'] = {}
        for key, value in dictionary.iteritems():
            if type(value) == dict:
                self.__dict__['dictionary'][key] = BSPDictionary(value)
            else:
                self.__dict__['dictionary'][key] = value
        self.__dict__['_len'] = len(self.dictionary) + len(self.dictionary['lumps'])
        
    def __getattr__(self, attr):
        if attr in self.dictionary:
            return self.dictionary[attr]
        elif attr in self.dictionary['lumps']:
            return self.dictionary['lumps'][attr]
        return self.dictionary.__getattribute__(attr)
        
    def __getitem__(self, item):
        if item in self.dictionary:
            return self.dictionary[item]
        elif item in self.dictionary['lumps']:
            return self.dictionary['lumps'][item]
        else:
            return self.dictionary[item]
        
    def __contains__(self, thing):
        return thing in self.dictionary
        
    def __len__(self):
        return self._len
        
    def keys(self):
        return self.dictionary.keys() + self.dictionary['lumps'].keys()
    
    def __repr__(self):
        return 'bsplib.BSPHeaders of %s' % self.name
    
    def __str__(self):
        return str(self.dictionary)
        
        
class BSPBody(ReadOnly):
    def __init__(self, reader, headers, name):
        self.__dict__['reader'] = reader
        self.__dict__['headers'] = headers
        self.__dict__['name'] = name
        self.__dict__['mapname'] = name[:-4]
        self.__dict__['parsed_lumps'] = {}
        
    def __getattr__(self, attr):
        if not attr in lumps:
            raise BSPNoSuchLumpError, attr
        if attr in self.parsed_lumps:
            return self.parsed_lumps[attr]
        if attr in converters:
            lump = BSPLump(attr, self.reader, self.headers, self.mapname)
        else:
            lump = BSPNotImplementedYetLump()
        self.parsed_lumps[attr] = lump
        return lump
    __getitem__ = __getattr__
    
    def parse(self, lumpname):
        if not lumpname in self.parsed_lumps:
            if lumpname in converters:
                lump = BSPLump(lumpname, self.reader, self.headers, self.mapname)
            else:
                lump = BSPNotImplementedYetLump(lumpname, self.name)
            self.parsed_lumps[lumpname] = lump
    
    def parseall(self):
        for lumpname in lumps:
            self.parse(lumpname)
    
    @staticmethod
    def __len__():
        return len(lumps)
        
    @staticmethod
    def keys():
        return lumps
    
    def __repr__(self):
        return 'bsplib.BSPBody of %s' % self.name
    
    def getDict(self):
        self.parseall()
        d = {}
        for lump in self.parsed_lumps.values():
            d[lump.lumpname] = lump.array
        return d
        
    def __str__(self):
        return str(self.getDict())

       
class BSPNotImplementedYetLump(ReadOnly):
    def __init__(self, lumpname, mapname):
        warn('FIXME (NIY): %s' % lumpname)
        self.__dict__['lumpname'] = lumpname
        self.__dict__['mapname']  = mapname
    def __getattr__(self, attr):
        return 'NotImplementedYet'
    __getitem__ = __getattr__
    
    def __repr__(self):
        return 'bsplib.BSPNotImplementedYetLump %s of %s' % (self.lumpname, self.mapname)
        
    def __str__(self):
        return repr(self)
        
        
class BSPLump(ReadOnly):
    def __init__(self, lumpname, reader, headers, mapname):
        lump = converters[lumpname](reader,
                                    headers['lumps'][lumpname],
                                    lumpname,
                                    headers['lumps'][lumpname]['version'])
        self.__dict__['lumpname'] = lumpname
        self.__dict__['mapname']  = mapname
        self.__dict__['array'] = lump.convert()
        self.__dict__['_len'] = len(self.array)
        
    def __getitem__(self, item):
        return self.array[item]
        
    def __getattr__(self, attr):
        return self.array.__getattribute__(attr)
        
    def __contains__(self, thing):
        return thing in self.array
        
    def __len__(self):
        return self._len
    
    def __repr__(self):
        return 'bsplib.BSPLump %s of %s' % (self.lumpname, self.mapname)
    
    def __str__(self):
        return str(self.array)
        

class BSPDictionary(ReadOnly):
    def __init__(self, dictionary):
        self.__dict__['dictionary'] = {}
        for key, value in dictionary.iteritems():
            if type(value) == dict:
                self.__dict__['dictionary'][key] = BSPDictionary(value)
            else:
                self.__dict__['dictionary'][key] = value
        self.__dict__['_len'] = len(self.dictionary)
        
    def __getattr__(self, attr):
        if attr in self.dictionary:
            return self.dictionary[attr]
        return self.dictionary.__getattribute__(attr)
        
    def __getitem__(self, item):
        return self.dictionary[item]
        
    def __contains__(self, thing):
        return thing in self.dictionary
        
    def __len__(self):
        return self._len
        
    def keys(self):
        return self.dictionary.keys()
    
    def __str__(self):
        return str(self.dictionary)

    def __repr__(self):
        return 'ReadOnly: %s' % repr(self.dictionary)
        

### BODY LUMP CONVERTERS ###
class BaseLump(object):
    def __init__(self, reader, lump, lumpname, version):
        self.read = reader.read
        self.getsize = reader.getsize
        self.lump = lump
        self.lumpname = lumpname
        self.version = version
        
    def convert(self):
        return 'Not Implemented Yet'

class SimpleLump(BaseLump):
    # format_version_0 = ''
    def __init__(self, reader, lump, lumpname, version):
        BaseLump.__init__(self, reader, lump, lumpname, version) # init the parent
        self.format = self.versionSupport(version)
        self.version = version
        if not self.format: # check support
            warn('FIXME: The lump %s does not have support for VBSP version %s' % (self.lumpname, self.version))
        
    def versionSupport(self, version):
        if hasattr(self, 'format_version_%s' % version):
            return self.__getattribute__('format_version_%s' % version)
        return False
    
    def convert(self):
        if not self.format:
            return 'Version %s not supported by this lump' % self.version
        amount = self.lump['filelen'] / self.getsize(self.format)
        arraylist = []
        self.read(offset=self.lump['fileofs']) # goto start of lump in body
        for x in range(amount):
            arraylist.append(self.process(self.read(self.format), self.version))
        return arraylist
        
    @staticmethod
    def process(data, version):
        return data
        
class Planes(SimpleLump):
    """
struct dplane_t
{
	Vector	normal;	// normal vector
	float	dist;	// distance from origin
	int	type;	// plane axis identifier
};
struct Vector
{
	float x;
	float y;
	float z;
};

Mathematically, the plane is described by the set of points (x, y, z) in the equation:

F(x,y,z) = Ax By Cz D 
    """
    format_version_0 = '3ffi'
    
    @staticmethod
    def process(data, version):
        x,y,z,d,t = data
        return {'Vector':(x,y,z), 'dist': d, 'type': t}
    
class Vertexes(SimpleLump):
    """
The vertex lump (3) is an array of coordinates of all the vertices (corners) of brushes in the map geometry. Each vertex is a Vector of 3 floats (x, y, and z), giving 12 bytes per vertex. 
    """
    format_version_0 = '3f'
    
class Edges(SimpleLump):
    """
struct dedge_t
{
	unsigned short	v[2];	// vertex indices
};
    """
    format_version_0 = '2H'
    
    
class Surfedges(SimpleLump):
    """
The Surfedge lump (13), presumable short for surface edge, is an array of (signed) integers.
    """
    format_version_1 = 'i'
    
class Faces(BaseLump):
    """
struct dface_t
{
	unsigned short	planenum;		// the plane number
	byte		side;			// faces opposite to the node's plane direction
	byte		onNode;			// 1 of on node, 0 if in leaf
	int		firstedge;		// index into surfedges
	short		numedges;		// number of surfedges
	short		texinfo;		// texture info
	short		dispinfo;		// displacement info
	short		surfaceFogVolumeID;	// ?
	byte		styles[4];		// switchable lighting info
	int		lightofs;		// offset into lightmap lump
	float		area;			// face area in units^2
	int		LightmapTextureMinsInLuxels[2];	// texture lighting info
	int		LightmapTextureSizeInLuxels[2];	// texture lighting info
	int		origFace;		// original face this was split from
	unsigned short	numPrims;		// primitives
	unsigned short	firstPrimID;
	unsigned int	smoothingGroups;	// lightmap smoothing group
};
    """
    format_version_0 = 'H??ihhhh4?if2i2iiHHI'
    
    @staticmethod
    def process(data, version):
        p, s, o, f, n, t, d, sf, st1, st2, st3, st4, l, a, lmtm1, lmtm2, lmts1, lmts2, of, nump, fpid, sg = data
        return {'planenum': p,
                'side': s,
                'onNode': o,
                'firstedge': f,
                'numedges': n,
                'texinfo': t,
                'dispinfo': d,
                'surfaceFogVolumeID': sf,
                'styles': (st1, st2, st3, st4),
                'lightofs': l,
                'area': a,
                'LightmapTextureMinsInLuxels': (lmtm1, lmtm2),
                'LightmapTextureSizeInLuxels': (lmts1, lmts2),
                'origFace': of,
                'numPrims': nump,
                'firstPrimID': fpid,
                'smoothingGroups': sg
                }
    
class OriginalFaces(Faces): pass

brush_content_flag = {
 0: 'CONTENTS_EMPTY',
 1: 'CONTENTS_SOLID',
 2: 'CONTENTS_WINDOW',
 4: 'CONTENTS_AUX',
 8: 'CONTENTS_GRATE',
 16: 'CONTENTS_SLIME',
 32: 'CONTENTS_WATER',
 64: 'CONTENTS_MIST',
 128: 'CONTENTS_OPAQUE',
 256: 'CONTENTS_TESTFOGVOLUME',
 1024: 'CONTENTS_AREAPORTAL',
 2048: 'CONTENTS_PLAYERCLIP',
 4096: 'CONTENTS_MONSTERCLIP',
 8192: 'CONTENTS_CURRENT_0',
 16384: 'CONTENTS_MOVEABLE',
 32768: 'CONTENTS_CURRENT_90',
 65536: 'CONTENTS_CURRENT_180',
 131072: 'CONTENTS_CURRENT_270',
 4194304: 'CONTENTS_CURRENT_UP',
 8388608: 'CONTENTS_CURRENT_DOWN',
 16777216: 'CONTENTS_ORIGIN',
 33554432: 'CONTENTS_MONSTER',
 67108864: 'CONTENTS_DEBRIS',
 134217728: 'CONTENTS_DETAIL',
 268435456: 'CONTENTS_TRANSLUCENT',
 536870912: 'CONTENTS_LADDER',
 1073741824: 'CONTENTS_HITBOX'
}


class Brushes(SimpleLump):
    """
struct dbrush_t
{
	int	firstside;	// first brushside
	int	numsides;	// number of brushsides
	int	contents;	// contents flags
};
CONTENTS_EMPTY		0	// No contents
CONTENTS_SOLID		0x1	// an eye is never valid in a solid
CONTENTS_WINDOW		0x2	// translucent, but not watery (glass)
CONTENTS_AUX		0x4
CONTENTS_GRATE		0x8	// alpha-tested "grate" textures. Bullets/VIS pass through, but solids don't
CONTENTS_SLIME		0x10
CONTENTS_WATER		0x20
CONTENTS_MIST		0x40
CONTENTS_OPAQUE		0x80	// things that cannot be seen through (may be non-solid though)
CONTENTS_TESTFOGVOLUME	0x100	// can see into a fogvolume (water)
CONTENTS_MOVEABLE	0x4000
CONTENTS_AREAPORTAL	0x8000
CONTENTS_PLAYERCLIP	0x10000
CONTENTS_MONSTERCLIP	0x20000
CONTENTS_CURRENT_0	0x40000
CONTENTS_CURRENT_90	0x80000
CONTENTS_CURRENT_180	0x100000
CONTENTS_CURRENT_270	0x200000
CONTENTS_CURRENT_UP	0x400000
CONTENTS_CURRENT_DOWN	0x800000
CONTENTS_ORIGIN		0x1000000	// removed before bsping an entity
CONTENTS_MONSTER	0x2000000	// should never be on a brush, only in game
CONTENTS_DEBRIS		0x4000000
CONTENTS_DETAIL		0x8000000	// brushes to be added after vis leafs
CONTENTS_TRANSLUCENT	0x10000000	// auto set if any surface has trans
CONTENTS_LADDER		0x20000000
CONTENTS_HITBOX		0x40000000	// use accurate hitboxes on trace
    """
    format_version_0 = 'iii'
    
    @staticmethod
    def process(data, version):
        names = ('firstside','numsides','contents')
        return dict(zip(names,data))
    
class Brushsides(SimpleLump):
    """
struct dbrushside_t
{
	unsigned short	planenum;	// facing out of the leaf
	short		texinfo;	// texture info
	short		dispinfo;	// displacement info
	short		bevel;		// is the side a bevel plane?
};
    """
    format_version_0 = 'Hhhh'
    
    @staticmethod
    def process(data, version):
        names = ('planenum','texinfo','dispinfo','bevel')
        return dict(zip(names,data))
            
    
class Nodes(SimpleLump):
    """
struct dnode_t
{
	int		planenum;	// index into plane array
	int		children[2];	// negative numbers are -(leafs 1), not nodes
	short		mins[3];	// for frustom culling
	short		maxs[3];
	unsigned short	firstface;	// index into face array
	unsigned short	numfaces;	// counting both sides
	short		area;		// If all leaves below this node are in the same area, then
					// this is the area index. If not, this is -1.
	short		paddding;	// pad to 32 bytes length
};
    """
    format_version_0 = 'i2i3h3hHHhxx'
    
    @staticmethod
    def process(data, version):
        return Node(data)
        
        
class Node:
    def __init__(self, data):
        p, c1, c2, i1, i2, i3, x1, x2, x3, f, n, a = data
        self.planenum = p
        self.children = (c1,c2)
        self.firstchild = None
        self.secondchild = None
        self.mins = (i1, i2, i3)
        self.maxs = (x2, x2, x3)
        self.firstface = f
        self.numfaces = n
        self.area = a
        
    def makeChilds(self, bsp):
        one, two = self.children
        if one < 0:
            self.firstchild = bsp.body.Leafs[-1-one]
        else:
            self.firstchild = bsp.body.Nodes[one]
        if two < 0:
            self.secondchild = bsp.body.Leafs[-1-two]
        else:
            self.secondchild = bsp.body.Nodes[two]
        
    
class Leafs(SimpleLump):
    """
struct dleaf_t
{
	int				contents;			// OR of all brushes (not needed?)

	short			cluster;

	short			area:9;
	short			flags:7;			// Per leaf flags.

	short			mins[3];			// for frustum culling
	short			maxs[3];

	unsigned short	firstleafface;
	unsigned short	numleaffaces;

	unsigned short	firstleafbrush;
	unsigned short	numleafbrushes;
	short			leafWaterDataID; // -1 for not in water

	// NOTE: removed this for version 1 and moved into separate lump "LUMP_LEAF_AMBIENT_LIGHTING" or "LUMP_LEAF_AMBIENT_LIGHTING_HDR"
	// Precaculated light info for entities.
	//CompressedLightCube m_AmbientLighting;
};
    """
    format_version_1 = 'ihh3h3hHHHHhxx' # VBSP20
    format_version_0 = 'ihh3h3hHHHHh24sxx' # VBSP19
    
    @staticmethod
    def process(data, version):
        return Leaf(data, version)


class Leaf:
    def __init__(self, data, version):
        if version == 1:
            con, clu, aaf, i1, i2, i3, x1, x2, x3, fir, num, flb, nlb, lwd = data
        else:
            con, clu, aaf, i1, i2, i3, x1, x2, x3, fir, num, flb, nlb, lwd, blah = data
        self.contents = con
        self.cluster = clu
        self.area_and_flags = aaf
        self.mins = (i1, i2, i3)
        self.maxs = (x1, x2, x3)
        self.firstLeafFace = fir
        self.numLeafFaces = num
        self.firstLeafBrush = flb
        self.numLeafBrushes = nlb
        self.leafWaterDataID = lwd
        
        self.isSolid = self.contents & 1
    
    
class LeafFaces(SimpleLump):
    """
    The leafface lump (16) is an array of shorts which are used to map from faces referenced in the leaf structure to indices in the face array. The leafbrush lump (17) does the same thing for brushes referenced in leaves.
    """
    format_version_0 = 'h'

class LeafBrushes(LeafFaces): pass

class TexInfo(SimpleLump):
    """
struct texinfo_t
{
	float	textureVecs[2][4];	// [s/t][xyz offset]
	float	lightmapVecs[2][4];	// [s/t][xyz offset] - length is in units of texels/area
	int	flags;			// miptex flags	overrides
	int	texdata;		// Pointer to texture name, size, etc.
}
The flags entry contains bitflags which are defined in bspflags.h: 
SURF_LIGHT	0x0001	// value will hold the light strength
SURF_SLICK	0x0002	// effects game physics
SURF_SKY	0x0004	// don't draw, but add to skybox
SURF_WARP	0x0008	// turbulent water warp
SURF_TRANS	0x0010	// surface is transparent
SURF_WET	0x0020	// the surface is wet
SURF_FLOWING	0x0040	// scroll towards angle
SURF_NODRAW	0x0080	// don't bother referencing the texture
SURF_HINT	0x0100	// make a primary bsp splitter
SURF_SKIP	0x0200	// completely ignore, allowing non-closed brushes
SURF_NOLIGHT	0x0400	// Don't calculate light on this surface
SURF_BUMPLIGHT	0x0800	// calculate three lightmaps for the surface for bumpmapping
SURF_NOSHADOWS	0x1000	// Don't receive shadows
SURF_NODECALS	0x2000	// Don't receive decals
SURF_NOCHOP	0x4000	// Don't subdivide patches on this surface
SURF_HITBOX	0x8000	// surface is part of a hitbox
    """
    format_version_0 = '8f8fii'
    
    @staticmethod
    def process(data, version):
        tsx, tsy, tsz, tso, ttx, tty, ttz, tto, lsx, lsy, lsz, lso, ltx, lty, ltz, lto , flags, texdata = data
        names = ('x','y','z','offset')
        return {'textureVecs':  {'s': dict(zip(names, (tsx,tsy,tsz,tso))),
                                 't': dict(zip(names, (ttx,tty,ttz,tto))),
                                },
                'lightmapVecs': {'s': dict(zip(names, (lsx,lsy,lsz,lso))),
                                 't': dict(zip(names, (ltx,lty,ltz,lto))),
                                },
                'flags': flags,
                'texdata': texdata
               }
                               
    
class Texdata(SimpleLump):
    """
struct dtexdata_t
{
	Vector	reflectivity;		// RGB reflectivity
	int	nameStringTableID;	// index into TexdataStringTable
	int	width, height;		// source image
	int	view_width, view_height;
};
    """
    format_version_0 = '3fi2i2i'
    
    @staticmethod
    def process(data, version):
        x,y,z,n,w,h,vw,vh = data
        return {'Vector': (x,y,z),
                'nameStringTableID': n,
                'width': w,
                'height': h,
                'view_width': vw,
                'view_heigth': vh}
    
class TexdataStringData(BaseLump):
    """
The TexdataStringData lump consists of concatenated null-terminated strings giving the texture name. 
    """
    def convert(self):
        self.read(offset=self.lump['fileofs']) # goto start of lump in body
        return self.read('%ss' % self.lump['filelen']).split('\0')
    
class TexdataStringTable(SimpleLump):
    """
The TexdataStringTable (lump 44) is an array of integers which are offsets into the TexdataStringData (lump 43). 
    """
    format_version_0 = 'i'
    
class Models(SimpleLump):
    """
The model lump (14) consists of an array of 24-byte dmodel_t structures: 
struct dmodel_t
{
	Vector		mins, maxs;
	Vector		origin;			// for sounds or lights
	int			headnode;
	int			firstface, numfaces;	// submodels just draw faces
										// without walking the bsp tree
};
Mins and maxs are the bounding points of the model. Origin is the coordinates of the model in the world, if set. Headnode is the index of the top node in the node array of the BSP tree which describes this model. Firstface and numfaces index into the face array and give the faces which make up this model. 
    """
    format_version_0 = '3f3f3fi2i'
    def convert(self):
        return 'Not Implemented Yet' # the format is size 48, should be 24!!!
    
class Visibility(BaseLump):
    """
struct dvis_t
{
	int	numclusters;
	int	byteofs[numclusters][2]
};
        unpacker = struct.Struct(self.format)
        amount = len(self.data) / unpacker.size
        arraylist = []
        for x in range(amount):
            current = self.data[x * unpacker.size:(x + 1) * unpacker.size]
            arraylist.append(self.process(unpacker.unpack(current)))
        return arraylist
    """
    def convert(self):
        """
        # gets a negative restlen - struct.Struct(byteofsformat).size!
        restdata = self.data
        arr = []
        while restdata:
            restlen  = len(restdata)
            numclusterreader = struct.Struct('i%ss' % (restlen - struct.Struct('i').size))
            numclusters, restdata = numclusterreader.unpack(restdata)
            restlen  = len(restdata)
            byteofsformat = '2i' * int(numclusters)
            format = '%s%ss' % (byteofsformat, restlen - struct.Struct(byteofsformat).size)
            print format
            byteofsreader = struct.Struct(format)
            byteofs_and_data = list(byteofsreader.unpack(restdata))
            restdata = byteofs_and_data.pop(-1)
            arr.append({'numclusters': numclusters, 'byteofs': byteofs_and_data})
        return arr # Really?
        """
        return 'NotImplementedYet' # sorry...

class Entities(BaseLump):
    """
The entity lump (0) is an ASCII text buffer, and stores the entity data in a format very similar to that used in the pre-compiled vmf files.
    """
    def convert(self):
        self.read(offset=self.lump['fileofs']) # goto start of lump in body
        return self.read('%ss' % self.lump['filelen'])

class GameLump(BaseLump):
    """
The Game lump (35) seems to be intended to be used for map data that is specific to a particular game using the Source engine, so that the file format can be extended without altering the previously defined format. It starts with a game lump header:

struct dgamelumpheader_t
{
	int lumpCount;	// number of game lumps
	dgamelump_t gamelump[lumpCount];
};

where the gamelump directory array is defined by:

struct dgamelump_t
{
	int		id;		// gamelump ID
	unsigned short	flags;		// flags
	unsigned short	version;	// gamelump version
	int		fileofs;	// offset to this gamelump
	int		filelen;	// length
};

The gamelump is identified by the 4-byte id member, which defines what data is stored in it, and the byte position of the data (from the start of the file) and its length is given in fileofs and filelen.

Of interest is the gamelump which is used to store prop_static entities, which uses the gamelump ID of 'sprp' ASCII (1936749168 decimal). Unlike most other entities, prop_statics are not stored in the entity lump. The gamelump formats used in HL2 are defined in the public/gamebspfile.h header file.

The first element of the prop_static game lump is the dictionary; this is an integer count followed by the list of model (prop) names used in the map:

struct StaticPropDictLump_t
{
	int	dictEntries;
	char	name[dictEntries];	// model name
};

Each name entry is 128 characters long, null-padded to this length.

Following the dictionary is the leaf array:

struct StaticPropLeafLump_t
{
	int leafEntries;
	unsigned short	leaf[leafEntries];
};

Presumably, this array is used to index into the leaf lump to locate the leaves that each prop static is located in. Note that a prop static may span several leaves.

Next, an integer giving the number of StaticPropLump_t entries, followed by that many structures themselves:

struct StaticPropLump_t
{
	Vector		Origin;		// origin
	QAngle		Angles;		// orientation (pitch roll yaw)
	unsigned short	PropType;	// index into model name dictionary
	unsigned short	FirstLeaf;	// index into leaf array
	unsigned short	LeafCount;
	unsigned char	Solid;		// solidity type
	unsigned char	Flags;
	int		Skin;		// model skin numbers
	float		FadeMinDist;
	float		FadeMaxDist;
	Vector		LightingOrigin;		// for lighting
	float		ForcedFadeScale;	// only present in version 5 gamelump
};


The coordinates of the prop are given by the Origin member; its orientation (pitch, roll, yaw) is given by the Angles entry, which is a 3-float vector. The PropType element is an index into the dictionary of prop model names, given above. The other elements correspond to the location of the prop in the BSP structure of the map, its lighting, and other entity properties as set in Hammer. The last element (ForcedFadeScale) is only present in the prop_static structure if the gamelump is specified as version 5 (dgamelump_t.version above); both version 4 and version 5 static prop gamelumps are used in official HL2 maps.

Other gamelumps used in HL2 BSP files are the detail prop gamelump (ID is 'dprp'), and the detail prop lighting lump (ID: 'dplt'). These are used for the prop_detail entities (grass tufts, etc.) automatically emitted by certain textures when placed on displacement surfaces. In version 20 BSP files there is also another gamelump (ID: 'dplh') which is probably related to HDR lighting of detail props.

There does not seem to be a specified limit on the size of the game lump. 
    """
    def convert(self):
        """
        headers = {}
        rlen = len(self.data) - 4
        count, rest = struct.unpack('i%ss' % rlen, self.data)
        headers['lumpCount'] = count
        gamelumpstruct = 'iHHii' * count
        s = struct.Struct(gamelumpstruct)
        rlen = len(rest) - s.size
        game = list(struct.unpack('%s%ss' % (gamelumpstruct, rlen), rest))
        headers['gamelumps'] = []
        for x in range(count):
            i, f, v, o, l = game.pop(0),game.pop(0),game.pop(0),game.pop(0),game.pop(0)
            headers['gamelumps'].append({'id':i, 'flags':f, 'version':v, 'fileofs': o, 'filelen': l})
        """
        return 'Not Implemented Yet' # This is just too big to implement now...
    
class DispInfo(BaseLump):
    """
struct ddispinfo_t
{
	Vector			startPosition;		// start position used for orientation
	int			DispVertStart;		// Index into LUMP_DISP_VERTS.
	int			DispTriStart;		// Index into LUMP_DISP_TRIS.
	int			power;			// power - indicates size of surface (2^power	1)
	int			minTess;		// minimum tesselation allowed
	float			smoothingAngle;		// lighting smoothing angle
	int			contents;		// surface contents
	unsigned short		MapFace;		// Which map face this displacement comes from.
	int			LightmapAlphaStart;	// Index into ddisplightmapalpha.
	int			LightmapSamplePositionStart;	// Index into LUMP_DISP_LIGHTMAP_SAMPLE_POSITIONS.
	CDispNeighbor		EdgeNeighbors[4];	// Indexed by NEIGHBOREDGE_ defines.
	CDispCornerNeighbors	CornerNeighbors[4];	// Indexed by CORNER_ defines.
	unsigned long		AllowedVerts[ALLOWEDVERTS_SIZE];	// active verticies
};
    """
    def convert(self):
        return 'Not Implemented Yet' # Don't understand CDispNeighbor and CDispCornerNeighbors type.
        # Also needed the value of ALLOWEDVERTS_SIZE for this
    
class DispVerts(SimpleLump):
    """
struct dDispVert
{
	Vector	vec;	// Vector field defining displacement volume.
	float	dist;	// Displacement distances.
	float	alpha;	// "per vertex" alpha values.
};
    """
    format_version_0 = '3fff'
    
    @staticmethod
    def process(data, version):
        x,y,z,d,a = data
        return {'Vector': (x,y,z),
                'dist': d,
                'alpha': a
               }
    
    
tri_flags = {
 1: 'DISPTRI_TAG_SURFACE',
 2: 'DISPTRI_TAG_WALKABLE',
 4: 'DISPTRI_TAG_BUILDABLE',
 8: 'DISPTRI_FLAG_SURFPROP1',
 16:'DISPTRI_FLAG_SUFRPROP2',
}
class DispTris(SimpleLump):
    """
struct dDispTri
{
	unsigned short Tags;	// Displacement triangle tags.
};

where the flags are:

DISPTRI_TAG_SURFACE	1
DISPTRI_TAG_WALKABLE	2
DISPTRI_TAG_BUILDABLE	4
DISPTRI_FLAG_SURFPROP1	8
DISPTRI_FLAG_SURFPROP2	16
    """
    format_version_0 = 'H'
    
class Pakfile(BaseLump):
    """
The Pakfile lump (40) is a special lump that can contains multiple files which are embedded into the bsp file. Usually, they contain special texture (.vtf) and material (.vmt) files which are used to store the reflection maps from env_cubemap entities in the map; these files are built and placed in the Pakfile lump when the "buildcubemaps" console command is executed. The Pakfile can optionally contain such things as custom textures and prop models used in the map, and are placed into the bsp file by using the BSPZIP program (or alternate programs such as [pakrat.html Pakrat]). These files are integrated into the game engine's filesystem and will be loaded preferentially before externally located files are used.

The format of the Pakfile lump is identical to that used by the Zip compression utility when no compression is specified (i.e., the individual files are stored in uncompressed format). If the Pakfile lump is extracted and written to a file, it can therefore be opened with WinZip and similar programs.

The header public/zip_uncompressed.h defines the structures present in the Pakfile lump. The last element in the lump is a ZIP_EndOfCentralDirRecord structure. This points to an array of ZIP_FileHeader structures immediately preceeding it, one for each file present in the Pak. Each of these headers then point to ZIP_LocalFileHeader structures that are followed by that file's data.

The Pakfile lump is usually the last element of the bsp file. 
    """
    def convert(self):
        return 'Not Implemented Yet' # Don't understand this lump
    
class Cubemaps(SimpleLump):
    """
struct dcubemapsample_t
{
	int		origin[3];	// position of light snapped to the nearest integer
	unsigned char	size;		// resolution of cubemap, 0 - default
};
    """
    format_version_0 = 'iiiB'
    
    @staticmethod
    def process(data,version):
        x,y,z,s = data
        return {'origin':(x,y,z), 'size': s}
    
class Overlays(SimpleLump):
    """
Unlike the simpler decals (infodecal entities), info_overlays are removed from the entity lump and stored separately in the Overlay lump (45). The structure is reflects the properties of the entity in Hammer almost exactly:

struct doverlay_t
{
	int		Id;
	short		TexInfo;
	unsigned short	FaceCountAndRenderOrder;
	int		Ofaces[OVERLAY_BSP_FACE_COUNT];
	float		U[2];
	float		V[2];
	Vector		UVPoints[4];
	Vector		Origin;
	Vector		BasisNormal;
};

The FaceCountAndRenderOrder member is split into two parts; the lower 14 bits are the number of faces that the overlay appears on, with the top 2 bits being the render order of the overlay (for overlapping decals). The Ofaces array, which is 64 elements in size (OVERLAY_BSP_FACE_COUNT) are the indices into the face array indicating which map faces the overlay should be displayed on. The other elements set the texture, scale, and orientation of the overlay decal. There can be a maximum of 512 overlays per file (MAX_MAP_OVERLAYS). 
    """
    format_version_0 = 'ihH64i2f2f12f3f3f'
    
    @staticmethod
    def process(data,version):
        # just too much to write it without help
        data = list(data)
        d = {}
        d['Id'] = data.pop(0)
        d['TexInfo'] = data.pop(0)
        d['Ofaces'] = []
        for x in range(64):
            d['Ofaces'].append(data.pop(0))
        d['U'] = (data.pop(0),data.pop(0))
        d['V'] = (data.pop(0),data.pop(0))
        d['UVPoints'] = []
        for x in range(4):
            d['UVPoints'].append((data.pop(0),data.pop(0),data.pop(0)))
        d['Origin'] = (data.pop(0),data.pop(0),data.pop(0))
        d['BasisNormal'] = (data.pop(0),data.pop(0),data.pop(0))
        return d
        
    
class Lighting(BaseLump):
    """
The lighting lump (8) is used to store the static lightmap samples of map faces. Each lightmap sample is a colour tint that multiplies the colours of the underlying texture pixels, to produce lighting of varying intensity. These lightmaps are created during the VRAD phase of map compilation and are referenced from the dface_t structure. The current lighting lump version is 1.

Each dface_t may have a up to four lightstyles defined in its styles[] array (which contains 255 to represent no lightstyle). The number of luxels in each direction of the face is given by the two LightmapTextureSizeInLuxels[] members (plus 1), and the total number of luxels per face is thus (LightmapTextureSizeInLuxels[0] 1) * (LightmapTextureSizeInLuxels[1] 1).

Each face gives a byte offset into the lighting lump in its lightofs member (if no lighting information is used for this face e.g. faces with skybox, nodraw and invisible textures, lightofs is -1.) There are (number of lightstyles)*(number of luxels) lightmap samples for each face, where each sample is a 4-byte ColorRGBExp32 structure:

struct ColorRGBExp32
{
	byte r, g, b;
	signed char exponent;
};

Standard RGB format can be obtained from this by multiplying each colour component by 2^(exponent). For faces with bumpmapped textures, there are four times the usual number of lightmap samples, presumably containing samples used to compute the bumpmapping.

Immediately preceeding the lightofs-referenced sample group, there are single samples containing the average lighting on the face, one for each lightstyle, in reverse order from that given in the styles[] array.

Version 20 BSP files contain a second, identically sized lighting lump in lump 53. This is presumed to store more accurate (higher-precision) HDR data for each lightmap sample. The format is currently unknown, but is also 32 bits per sample.

The maximum size of the lighting lump is 0x1000000 bytes, i.e. 16 Mb (MAX_MAP_LIGHTING). 
    """
    # is version 1 in VBSP19 and VBSP20
    def convert(self):
        return 'Not Implemented Yet' # Don't understand this lump
    
    
class LightingHDR(BaseLump):
    # is version 1 in VBSP19 and VBSP20
    def convert(self):
        return 'Not Implemented Yet'
    
    
class Occlusion(BaseLump):
    # is version 2 in VBSP19 and VBSP20
    def convert(self):
        return 'Not Implemented Yet'
        
    
class Other(BaseLump): # PseudoClass
    """
There are nineteen other lumps defined in the HL2 BSP file format that have not yet been covered. These lumps were not needed for the creation of a decompiler, and so I have not researched them or their formats. There are also four lumps only present in version 20 BSP files. I will give general information and likely guesses to the content of these lumps.

The Occlusion lump (9) contains data on func_occluder entities which are switchable entities that block the drawing of visible entities behind them.

The Worldlights lump (15) contains information on each static light entity in the world, and seems to be used to provide semi-dynamic lighting for moving entities.

The Areas lump (20) references the Areaportals lump (21) and is used with func_areaportal and func_areaportalwindow entities to define sections of the map that can be switched to render or not render.

The Portals (22), Clusters (23), PortalVerts (24), ClusterPortals (25), and ClipPortalVerts (41) lumps are used by the VVIS phase of the compile to ascertain which clusters can see which other clusters. A cluster is a player-enterable leaf volume in the map (see above). A "portal" is a polygon boundary between a cluster or leaf and an adjacent cluster or leaf. Most of this information is also used by the VRAD program to calculate static lighting, and then is removed from the bsp file.

Lumps 29 (PhysCollide) and 49 (PhysCollideSurface) seem to be related to the physical simulation of entity collisions in the game engine.

The VertNormal (30) and VertNormalIndices (31) lumps may be related to smoothing of lightmaps on faces.

The FaceMacroTextureInfo lump (47) is a short array containing the same number of members as the number of faces in the map. If the entry for a face contains anything other than -1 (0xFFFF), it is an index of a texture name in the TexDataStringTable. In VRAD, the corresponding texture is mapped onto the world extents, and used to modulate the lightmaps of that face. There is also a base macro texture (located at materials/macro/mapname/base.vtf) that is applied to all faces if found. Only maps in VTMB seem to make any use of macro textures.

LeafWaterData (36) and LeafMinDistToWater (46) lumps may be used to determine player position with respect to water volumes.

The Primitives (37), PrimVerts (38) and PrimIndices (39) lumps are used in reference to "non-polygonal primitives". They are also sometimes called "waterstrips", "waterverts" and "waterindices" in the SDK Source, since they were originally only used to subdivide water meshes. They are now used to prevent the appearance of cracks between adjacent faces, if the face edges contain a "T-junction" (a vertex collinearly between two other vertices). The PrimIndices lump defines a set of triangles between face vertices, that tessellate the face. They are referenced from the Primatives lump, which is in turn referenced by the face lump data. Current maps do not seem to use the PrimVerts lump at all. (Ref.)

Version 20 files containing HDR lighting information have four extra lumps, the contents of which are currently uncertain. Lump 53 is always the same size as the standard lighting lump (8) and probably contains higher-precision data for each lightmap sample. Lump 54 is the same size as the worldlight lump (15) and presumably contains HDR-related data for each light entity. Lumps 55 and 56 both seem to be 24-byte records (possibly CompressedLightCube structures) with the same count as the number of leaves in the map. They are probably thus HDR-related per-leaf lighting information. 
    """
    def convert(self):
        return 'Not Implemented Yet' # TO BE DONE
    

        
# Converters list
def classcheck(thing):
    try:
        if issubclass(thing,BaseLump):
            return True
        else:
            return False
    except:
        return False
converters   = dict(filter(lambda x: classcheck(x[1]), globals().iteritems()))

### Expermintal functions
"""
The following functions are highly experimental and untested! Most take bsp as
first argument, if everything goes well they'll become part of the BSP class or
a subclass (body).
"""

def getLeaf(bsp, position):
    """
    Q: How does the engine determine which leaf the player is in?
A: It means that the program starts at the head node, and then goes down to one
of the children, depending on which side of the partition the player is in.
That node becomes the current node, and then the process is repeated, until the
current node is a leaf, in which case the engine knows where the player is!

This process is called recursing the BSP tree. 
    """
    if type(position) in (list, tuple):
        x, y, z = position
    else:
        x, y, z = position['x'], position['y'], position['z']
    for leaf in bsp.body.Leafs:
        xhi, yhi, zhi = leaf.maxs
        xlo, ylo, zlo = leaf.mins
        if x > xhi:
            continue
        if x < xlo:
            continue
        if y > yhi:
            continue
        if y < ylo:
            continue
        if z > zhi:
            continue
        if z < zlo:
            continue
        return leaf
    return None

# F(x,y,z) = Ax By Cz D 
def planefunc(x, y, z, plane):
    A, B, C = plane['Vector']
    D = plane['dist']
    return (A * x) + (B * y) + (C * z) + D

def checknode(bsp, currentnode, start, end):
    """
checknode (currentnode)
    if(currentnode is a leaf)
        if(currentnode contents are solid)
            return HIT
        else
            return MISS

    if(side start is on = side end is on)
        return checknode (child of currentnode both sides are on)

    result1 = checknode (child of currentnode start is on)
    result2 = checknode (child of currentnode end is on)
    if(result1 does not equal result2)
        nodehit = currentnode
    if(result1 = HIT or result2 = HIT)
        return HIT
    else
        return MISS 
    """
    if isinstance(currentnode, Leaf):
        if currentnode.isSolid:
            return 'HIT'
        return 'MISS'
    if not currentnode.firstchild:
        currentnode.makeChilds(bsp)
    # on the plane (F=0), in front of the plane (F>0), and behind the plane (F<0).
    plane = bsp.Planes[currentnode.planenum]
    sPos = planefunc(start[0], start[1], start[2], plane)
    ePos = planefunc(end[0], end[1], end[2], plane)
    if sPos > 0 and ePos > 0:
        # in front of plane => firstchild
        return checknode(bsp, currentnode.firstchild, start, end)
    elif sPos < 0 and ePos < 0:
        # behind plane => secondchild
        return checknode(bsp, currentnode.secondchild, start, end)
    else:
        res1 = checknode(bsp, currentnode.firstchild, start, end)
        res2 = checknode(bsp, currentnode.secondchild, start, end)
        if res1 == 'HIT' or res2 == 'HIT':
            return 'HIT'
        return 'MISS'

def isWallBetween(bsp, start, end):
    """
    There's gotta be a way to speed things up here! up to 0.2 seconds on de_dust
    for a traceline is not acceptable
    """
    headnode = bsp.body.Nodes[0]
    return checknode(bsp, headnode, start, end) == 'HIT'

# CLI Functions
"""
Functions below are for command line interface only. As of now this interface is
only inteded for rough debugging/checking of the lib.
"""

def convert_body(body, lump_info):
    warn('WARNING: For CLI only')
    bodydict = {}
    for lumpname, lump in lump_info.iteritems():
        if lumpname in converters:
            converter = converters[lumpname](body, lump)
            bodydict[lumpname] = converter.convert()
        else:
            bodydict[lumpname] = 'not implemented yet'
    return bodydict

if __name__ == '__main__':
    """
    import pprint
    import optparse
    parser = optparse.OptionParser()
    parser.add_option("-i", "--infile", action="store", dest="infile", default='/home/jonas/srcds/cstrike/maps/de_dust.bsp')
    parser.add_option("-p", "--prettyfile", action="store", dest="prettyfile", default='/home/jonas/Desktop/de_dust.pretty')
    (option, args) = parser.parse_args()
    bsp = BSP(option.infile)
    data = bsp.body.Leafs.arrayitems
    f = open(option.prettyfile,'wb')
    pprint.pprint(data,f)
    f.close()
    """
    import pprint
    import optparse
    import cPickle
    parser = optparse.OptionParser()
    parser.add_option('-n', '--nowrite', action='store_true', dest='nowrite', default=False)
    parser.add_option("-i", "--infile", action="store", dest="infile", default='de_dust.bsp')
    parser.add_option("-p", "--prettyfile", action="store", dest="prettyfile", default='de_dust.pretty')
    (option, args) = parser.parse_args()
    bsp = BSP(option.infile)
    if not option.nowrite:
        f = open(option.prettyfile,'wb')
        pprint.pprint(bsp.getDict(),f)
        f.close()
    isWallBetween(bsp, (1,2,3),(-4,-10,-30))
    
def loadBSP(bspfile):
    warn('WARNING: For testing only, do not use!')
    # ONLY FOR TESTING, DO NOT USE
    headers, raw_bsp = convert(bspfile)
    body = convert_body(raw_bsp, headers['lumps'])
    data = {'headers':headers, 'body':body}
    return data